//#include<bits/stdc++.h>
//using namespace std;
//#define int long long
//const int n = 1e9;
//struct point {
//	int x, y;
//};
//
//double dis(point a, point b)
//{
//	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
//}
//double Closest(point s[], int low, int high)
//{
//	double d1, d2, d3, d;
//	int mid, i, j, index;
//	point P[n];
//	if (high - low == 1)
//		return dis(s[low], s[high]);
//	if (high - low == 2) {
//		d1 = dis(s[low], s[low + 1]);
//		d2 = dis(s[low + 1], s[high]);
//		d3 = dis(s[low], s[high]);
//		if (d1 < d2 && d2 < d3) {
//			return d1;
//		} else if (d2 < d3) return d2;
//		else return d3;
//		mid = (low + high) / 2;
//		d1 = Closest(s, low, mid);
//		d2 = Closest(s, mid + 1, high);
//		if (d1 <= d2) d = d1;
//		else d = d2;
//		index = 0;
//		for (int i = mid; (i >= low) && (s[mid].x - s[i].x < d); i--) {
//			P[index++] = s[i];
//		}
//		for (int i = mid; (i <= high) && (s[i].x - s[mid].x < d); i++) {
//			P[index++] = s[i];
//		}
//		QuickSort(P, 0, index - 1);
//		for (int i = 0; i < index; i++) {
//			for (int j = i + 1; j < index; j++) {
//				if (P[j].y - P[i].y >= d)
//					break;
//				else {
//					d3 = dis(P[i], P[j]);
//					if (d3 < d) d = d3;
//				}
//			}
//		}
//
//	}
//	return d;
//}
//signed main()
//{
//// 生成数据
//	int n = 100;
//	point points[n];
//	srand(time(0));
//	for (int i = 0; i < n; i++) {
//		points[i].x = rand() % 1001;  // 生成0到1000之间的随机x坐标
//		points[i].y = rand() % 1001;  // 生成0到1000之间的随机y坐标
//	}
//
//// 调用Closest函数计算最近两个点的距离
//	double closestDistance = Closest(points, 0, n - 1);
//	cout << "The closest distance between two points is: " << closestDistance << endl;
//
//	return 0;
//}
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e9;

struct point {
	double x, y;
};

double dis(point a, point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void QuickSort(point A[], int low, int high) {
	if (low >= high)
		return;
	int i = low, j = high, pivot = A[low].x;
	while (i < j) {
		while (i < j && A[j].x >= pivot)
			j--;
		A[i] = A[j];
		while (i < j && A[i].x <= pivot)
			i++;
		A[j] = A[i];
	}
	A[i].x = pivot;
	QuickSort(A, low, i - 1);
	QuickSort(A, i + 1, high);
}

double Closest(point s[], int low, int high)
{
	if (high - low == 1)
		return dis(s[low], s[high]);
	if (high - low == 2) {
		double d1 = dis(s[low], s[low + 1]);
		double d2 = dis(s[low + 1], s[high]);
		double d3 = dis(s[low], s[high]);
		if (d1 < d2 && d1 < d3) {
			return d1;
		} else if (d2 < d3) {
			return d2;
		} else {
			return d3;
		}    
	}
	int mid = (low + high) / 2;
	double d1 = Closest(s, low, mid);
	double d2 = Closest(s, mid + 1, high);
	double d = min(d1, d2);
	
	point P[high - low + 1];
	int index = 0;
	for (int i = low; i <= high; i++) {
		if (abs(s[mid].x - s[i].x) < d) {
			P[index++] = s[i];
		}
	}
	QuickSort(P, 0, index - 1);
	for (int i = 0; i < index; i++) {
		for (int j = i + 1; j < index && P[j].y - P[i].y < d; j++) {
			double d3 = dis(P[i], P[j]);
			if (d3 < d) {
				d = d3;
			}
		}
	}
	return d;
}

signed main()
{
	// 生成数据
	int n = 10;
	point points[n];
	srand(time(0));
	
	for (int i = 0; i < n; i++) {
		points[i].x = (double)(rand() % 10000) / 1000; 
		points[i].y = (double)(rand() % 10000) / 1000;  
	}
	cout << "Randomly Init 10 datas:" <<endl; 
	for (int i = 0; i < n; i++) {
		cout <<points[i].x << " "
		<<points[i].y <<endl;
	}
	// 调用Closest函数计算最近两个点的距离
	double closestDistance = Closest(points, 0, n - 1);
	cout << "The closest distance between two points is: " << closestDistance << endl;
	
	return 0;
}
